# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 堆排序
# 基本思想: 在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，
# 在当前无序区中选择关键字最大(或最小)的记录。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

# 时间复杂度:最好O(nlogn)(已经排好序),最坏O(nlogn)(逆序),平均O(nlogn)
# 空间复杂度:最好0(已经排好序),最坏O(n)(逆序),平均O(1)
# 稳定性: 不稳定

# 从上到下遍历
from sort.arr_util import random_scale_arr


def heap_sort(num_arr):
    length = len(num_arr)
    pos = int((length - 2) / 2)
    while pos >= 0:
        heap_adjust(num_arr, pos, length - 1)
        pos -= 1
    for i in range(0, length - 1):
        tmp = num_arr[0]
        num_arr[0] = num_arr[length - 1 - i]
        num_arr[length - 1 - i] = tmp
        heap_adjust(num_arr, 0, length - 2 - i)


def heap_adjust(num_arr, start, end):
    tmp = num_arr[start]
    index = start * 2 + 1
    while index <= end:
        if index < end and num_arr[index] < num_arr[index + 1]:
            index += 1
        if tmp < num_arr[index]:
            num_arr[start] = num_arr[index]
            start = index
        else:
            break
        index = index * 2 + 1
    num_arr[start] = tmp


# 耗时,从下到上，不可取
def heap_sort2(num_arr):
    pos = len(num_arr) - 1
    while pos > 0:
        big_tree2(num_arr, pos)
        tmp = num_arr[0]
        for i in range(1, pos + 1):
            num_arr[i - 1] = num_arr[i]
        num_arr[pos] = tmp
        pos -= 1


def big_tree2(num_arr, pos):
    while True:
        flag = False
        index = pos
        while index > 0:
            mod = index % 2
            if mod == 0:
                parent = int((index - 2) / 2)
                if num_arr[index] > num_arr[parent]:
                    tmp = num_arr[index]
                    num_arr[index] = num_arr[parent]
                    num_arr[parent] = tmp
                    flag = True
            else:
                parent = int((index - 1) / 2)
                if num_arr[index] > num_arr[parent]:
                    tmp = num_arr[index]
                    num_arr[index] = num_arr[parent]
                    num_arr[parent] = tmp
                    flag = True
            index -= 1
        if not flag:
            break


if __name__ == '__main__':
    arr = [1, 2, 5, 7, 6, 5, 4]
    # arr = [4, 6, 3, 5, 9]
    heap_sort(arr)
    print(arr)
    arr2 = random_scale_arr(20, 500)
    heap_sort(arr2)
    print(arr2)
